import java.util.ArrayList;
import java.util.*;

public class ThreeSum {
    List<List<Integer>> src = new ArrayList<> ();

    public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        // 排序后 固定一个位置后, 双指针
        Arrays.sort(nums);

        for (int i = 0; i < n; i ++) {
            int a = nums[i];
            // 如果 a 已经大于 0 了, 就不可能组成 0
            if (a > 0)   break;
            // 去重
            if (i > 0 && nums[i] == nums[i - 1])
                continue ;

            int left = i + 1, right = n - 1;
            while (left < right) {
                //去重 1, 这里的去重 和 去重 2 是 等效的
                if (left > i + 1 && nums[left] == nums[left - 1]
                        && right < n - 1 && nums[right] == nums[right + 1]) {
                    left ++;
                    right --;
                    continue;
                }

                int sum = a + nums[left] + nums[right];
                if (sum > 0) {
                    right --;
                } else if (sum < 0) {
                    left ++;
                } else {
                    ArrayList<Integer> t = new ArrayList<> ();
                    t.add(a);
                    t.add(nums[left ++]);
                    t.add(nums[right --]);
                    src.add(t);
                    // 去重 2
                    // while (left < right && nums[left] == nums[left - 1])
                    //     left ++;
                    // while (left < right && nums[right] == nums[right + 1])
                    //     right --;
                }
            }
        }

        return src;
    }
}
